package algo;

import java.util.Stack;

public class LinkList {
	public static void main(String args[]) {
		ListNode head = new ListNode(-1);
		LinkNodeList link = new LinkNodeList();
		//link.addData(head, 1);
//		link.addData(head, 2);
		link.addData(head,3);
		//link.addData(head,4);
		link.addData(head,5);
		link.traverse(head);

		ListNode l1 = new ListNode(-1);
		link.addData(l1,1);
		link.addData(l1,2);
		link.addData(l1,3);


		ListNode l2= new ListNode(-1);
		link.addData(l2,4);
		link.addData(l2,5);
		link.addData(l2,6);
		link.addData(l2,8);
		link.addData(l2,8);
//		System.out.println("===========合并两个链表=======================");
//
//		ListNode listNode = link.mergeTwoLists(l1, l2.next);
//		link.traverse(listNode);
//
//
//		System.out.println("Length of Link: " + link.LinkListLength(head));
//
//		System.out.println("==========删除========================");
//
//		removeFromEnd(head, 1);
//
//		link.traverse(head);
//		System.out.println("Length of Link: " + link.LinkListLength(head));
//		System.out.println("==================================");
//
//		link.insert(head, 2, 0);
//		link.traverse(head);
//
//		System.out.println("==================================");
//		link.delete(head, 2);
//		link.traverse(head);
//
//		System.out.println("==============sort====================");
//		link.sort(head);
//		link.traverse(head);
//
//		System.out.println("==============deleteSame value====================");
//		link.deleteSame(head);
//		link.traverse(head);
//
//		System.out.println("==============searchMid====================");
//		ListNode s = link.searchMid(head);
//		link.traverse(head);
//		System.out.println("the mid of the linklist: " + s.val);
//
//		System.out.println("==============递归输出链表====================");
//		link.printListNode(head);
//
//		System.out.println("==============反转链表====================");
//		link.traverse(head);
//
//		System.out.println("==============反转前====================");
//		ListNode head1 = link.reverseLinkList(head);
//
//		System.out.println("==============反转后===================");
//		link.traverse(head1);

		System.out.println("==============局部反转前====================");
		ListNode head2 = link.reverseBetween(head,1,2);
		//ListNode listNode = link.reverseLink(head);

		System.out.println("==============局部反转后===================");
		link.traverse(head2);


		

	}

	public static ListNode removeFromEnd(ListNode head, int n) {
		if (head == null) {
			return null;
		}

		ListNode firstMove = head;
		ListNode needRemove = head;
		ListNode prevNeedRemove = null;

		if (firstMove.next == null) {
			return null;
		}

		for (int i = 0; i < n - 1; i++) {
			firstMove = firstMove.next;
		}

		while (firstMove.next != null) {
			prevNeedRemove = needRemove;
			needRemove = needRemove.next;
			firstMove = firstMove.next;
		}

		if (prevNeedRemove == null) {
			return head.next;
		} else {
			prevNeedRemove.next = needRemove.next;
			needRemove.next = null;
		}
		return head;
	}

}

class ListNode {
	int val;
	ListNode next;

	public ListNode() {
	}

	public ListNode(int val) {
		this.val = val;
	}

	public ListNode(int val, ListNode next) {
		this.val = val;
		this.next = next;
	}
}

class LinkNodeList {
	/**
	 * add Data to LinkList
	 */

	public void addData(ListNode head, int value) {

		ListNode newData = new ListNode(value);

		ListNode temp = head;

		while (temp.next != null) {
			temp = temp.next;
		}

		temp.next = newData;
	}

	public void traverse(ListNode head) {
		ListNode temp = head;

		while (temp != null) {
			System.out.println("LinkList: " + temp.val);
			temp = temp.next;
		}

	}

	public int LinkListLength(ListNode head) {
		int length = 0;
		ListNode temp = head.next;
		while (temp != null) {
			length++;
			temp = temp.next;
		}
		return length;

	}
	/**
	 * 
	 * @param head 头指针
	 * @param index 插入的位置
	 * @param val 插入的值
	 */
	
	public void insert(ListNode head,int index,int val) {
		if(index<1 || index > LinkListLength(head)) {
			System.out.println("插入位置不合法");
			return;
		}
		
		ListNode temp  = head.next;
		int currentPos = 0;
		
		ListNode insertVal = new ListNode(val);
		
		while(temp != null) {
			if(index-1 == currentPos) {
				insertVal.next = temp.next;
				temp.next = insertVal;
				return;
			}
			
			currentPos ++;
			temp = temp.next;
		}
		
	}
	
	public void delete(ListNode head,int index) {
		if(index < 1 || index > LinkListLength(head)) {
			System.out.println("删除位置不合法！");
			return;
		}
		
		ListNode temp = head.next;
		
		int currentPos = 0;
		
		while(temp != null) {
			if(currentPos == index-1) {
				temp.next = temp.next.next;
				
			}
			currentPos ++;
			temp = temp.next;
		}
	}
	
	public void sort(ListNode head) {
		ListNode currentNode;
		ListNode nextNode;
		
		for(currentNode = head.next;currentNode.next != null; currentNode = currentNode.next) {
			for(nextNode = head.next;nextNode.next !=null;nextNode = nextNode.next) {
				if(nextNode.val > nextNode.next.val) {
					int temp = nextNode.val;
					nextNode.val = nextNode.next.val;
					nextNode.next.val = temp;
				}
			}
		}
	}
	
	public void deleteSame(ListNode head) {
		ListNode temp = head.next;
		ListNode nextNode = head.next;
		
		while(temp.next != null) {
			while(nextNode.next != null) {
				if(nextNode.val == nextNode.next.val) {
					nextNode.next = nextNode.next.next;
				}else {
					nextNode = nextNode.next;
				}
			}
			temp = temp.next;
		}
	}
	
	
	public ListNode searchMid(ListNode head) {
		ListNode p1,p2;
		p1 = head.next;
		p2 = head.next;
		
		while(p2 != null
				&& p2.next != null && p2.next.next != null) {
			p1 = p1.next;
			p2 = p2.next.next;
		}
		return p1;
	}
	
	public void printListNode(ListNode head) {
		if(head != null) {
			printListNode(head.next);
			System.out.println("递归输出链表： " + head.val);
		}
	}
	
	public ListNode reverseLinkList(ListNode head) {
		if (head == null || head.next == null)
			return head;
		ListNode tmp = head.next;
		ListNode new_head = reverseLinkList(tmp);
		tmp.next = head;
		head.next = null;
		return new_head;
	}

	public ListNode reverseLink(ListNode head){
		if(head==null){
			return null;
		}
		ListNode tmp = head.next;
		ListNode p;
		Stack<ListNode> stack = new Stack<>();
		while (tmp!=null){
			stack.push(tmp);
			tmp = tmp.next;
		}
        ListNode newHead = new ListNode(-1);
		p = newHead;
		while (!stack.isEmpty()){
			ListNode s=stack.pop();
			s.next = p.next;
			p.next = s;
			p = p.next;
		}
		return newHead;
	}

	public ListNode reverseBetween(ListNode head, int left, int right) {
		ListNode res = new ListNode(-1);
		res.next = head.next;
		ListNode cur = res;
		for (int i = 1; i < left; i++) {
			cur = cur.next;
		}

		ListNode temp = cur.next;
		for (int i = 0; i < right - left; i++) {
			ListNode nxt = temp.next;
			temp.next = nxt.next;
			nxt.next = cur.next;
			cur.next = nxt;
		}

		return res.next;

	}

	/**
	 * 合并两个递增的链表
	 * @param l1
	 * @param l2
	 * @return
	 */

	public ListNode mergeTwoLists(ListNode l1, ListNode l2){
		ListNode head = new ListNode(0);
		ListNode node = head;

		while (l1!=null && l2 !=null){
			if(l1.val < l2.val){
				node.next = l1;
				l1 = l1.next;
			} else {
				node.next = l2;
				l2 = l2.next;
			}

			node = node.next;
		}

		//把没遍历到的补上
		node.next = l1 == null?l2:l1;
		return head.next;
	}

}
